import java.util.Stack;

/**
 * <p>二叉树</p>
 * <p>最常用的方法是把节点存放在无关联的存储器中，而通过每个节点中
 *    指向自己子节点的引用</p>
 *
 * @author fireway 2017/10/25
 */
class Node {
    public int mKey;
    public double mData;
    public Node mLeftChild;
    public Node mRightChild;

    public void displayNode() {
        System.out.print('{');
        System.out.print(mKey);
        // System.out.print(", ");
        // System.out.print(mData);
        System.out.print("} ");
    }
}

enum TraverseType {
    Preorder, Inorder, Postorder;
}

class Tree {
    private Node mRoot;

    public Node find(int key) {
        if (mRoot == null) {
            System.out.println("The tree is empty!!!");
            return null;
        }

        Node current = mRoot;

        while (current.mKey != key) {
            if (key < current.mKey) {
                current = current.mLeftChild;
            } else {
                current = current.mRightChild;
            }

            // 找不到结点
            // 到达序列末端而没有找到要找的结点，表明它不存在，返回null指出这种情况
            if (current == null) {
                return null;
            }
        }

        return current;
    }

    public void insert(int key, double data) {
        Node node = new Node();
        node.mKey = key;
        node.mData = data;

        if (null == mRoot) {
            mRoot = node;
        } else {
            Node current = mRoot;
            Node parent = null;
            while (true) {
                parent = current;
                if (key < current.mKey) {
                    current = current.mLeftChild;
                    if (null == current) {
                        parent.mLeftChild = node;
                        return;
                    }
                } else {
                    current = current.mRightChild;
                    if (null == current) {
                        parent.mRightChild = node;
                        return;
                    }
                }
            }
        }
    }

    public boolean delete(int key) {
        if (mRoot == null) {
            System.out.println("The tree is empty!!!");
            return false;
        }

        Node current = mRoot;
        Node parent = null;
        boolean isLeftChild = false;

        while (current.mKey != key) {
            parent = current;

            if (key < current.mKey) {
                current = current.mLeftChild;
                isLeftChild = true;
            } else {
                current = current.mRightChild;
                isLeftChild = false;
            }

            if (current == null) {
                return false;  // didn't find it
            }
        }

        if (current.mLeftChild == null && current.mRightChild == null) {
            if (current == mRoot) {
                mRoot = null;
            } else if (isLeftChild) {
                parent.mLeftChild = null;
            } else {
                parent.mRightChild = null;
            }
        } else if (current.mRightChild == null) {
            if (current == mRoot) {
                mRoot = mRoot.mLeftChild;
            } else if (isLeftChild) {
                parent.mLeftChild = current.mLeftChild;
            } else {
                parent.mRightChild = current.mLeftChild;
            }
        } else if (current.mLeftChild == null) {
            if (current == mRoot) {
                mRoot = mRoot.mRightChild;
            } else if (isLeftChild) {
                parent.mLeftChild = current.mRightChild;
            } else {
                parent.mRightChild = current.mRightChild;
            }
        } else {
            Node successor = getInorderSuccessor(current);

            if (current == mRoot) {
                mRoot = successor;
            } else if (isLeftChild) {
                parent.mLeftChild = successor;
            } else {
                parent.mRightChild = successor;
            }

            successor.mLeftChild = current.mLeftChild;
        }

        return true;
    }

    /**
     * 返回参数delNode的后续节点(中序遍历)
     */
    private Node getInorderSuccessor(Node delNode) {
        Node current = delNode.mRightChild;
        Node successorParent = null;
        Node successor = null;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.mLeftChild;
        }

        if (successor != delNode.mRightChild) {
            successorParent.mLeftChild = successor.mRightChild;
            successor.mRightChild = delNode.mRightChild;
        }

        return successor;
    }

    public void displayTree() {
        Stack<Node> globalStack = new Stack<Node>();
        globalStack.push(mRoot);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("......................................................");

        while (!isRowEmpty) {
            Stack<Node> localStack = new Stack<Node>();
            isRowEmpty = true;

            for (int j = 0; j < nBlanks; j++) {
                System.out.print(' ');
            }

            while (!globalStack.isEmpty()) {
                Node temp = (Node)globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.mKey);
                    localStack.push(temp.mLeftChild);
                    localStack.push(temp.mRightChild);

                    if (temp.mLeftChild != null || temp.mRightChild != null) {
                        isRowEmpty = false;
                    }
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }

                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }
            }
            System.out.println();
            System.out.println();
            nBlanks /= 2;
            while (!localStack.isEmpty()) {
                globalStack.push(localStack.pop());
            }
        }

        System.out.println("......................................................");
    }

    /**
     * 遍历
     */
    public void traverse(TraverseType traverseType) {
        switch (traverseType) {
            case Preorder:
                preOrder(mRoot);
                break;
            case Inorder:
                inOrder(mRoot);
                break;

            case Postorder:
                postOrder(mRoot);
                break;
        }
    }

    /**
     * 前序遍历：
     * 1. 访问节点
     * 2. 调用自身遍历该节点的左子树
     * 3. 调用自身遍历该节点的右子树
     *
     * @param localRoot
     */
    private void preOrder(Node currentRoot) {
        if (currentRoot == null) {
            return;
        }

        currentRoot.displayNode();
        preOrder(currentRoot.mLeftChild);
        preOrder(currentRoot.mRightChild);
    }

    /**
     * 中序遍历:
     * 1. 调用自身遍历该节点的左子树
     * 2. 访问节点
     * 3. 调用自身遍历该节点的右子树
     *
     * @param localRoot
     */
    private void inOrder(Node currentRoot) {
        if (currentRoot == null) {
            return;
        }

        inOrder(currentRoot.mLeftChild);
        currentRoot.displayNode();
        inOrder(currentRoot.mRightChild);
    }

    /**
     * 后序遍历:
     * 1. 调用自身遍历该节点的左子树
     * 2. 调用自身遍历该节点的右子树
     * 3. 访问节点
     *
     * @param localRoot
     */
    private void postOrder(Node currentRoot) {
        if (currentRoot == null) {
            return;
        }

        postOrder(currentRoot.mLeftChild);
        postOrder(currentRoot.mRightChild);
        currentRoot.displayNode();
    }

    /**
     * 获取最小值对应的节点
     */
    public Node getMininum() {
        Node current = mRoot;
        Node last = null;
        while (current != null) {    // start at root until the bottem
            last = current;           // remember node
            current = current.mLeftChild;    // go left child
        }

        return last;
    }

    /**
     * 获取最大值对应的节点
     */
    public Node getMaximum() {
        Node current = mRoot;
        Node parent = null;

        while (current != null) {
            parent = current;
            current = current.mRightChild;
        }

        return parent;
    }
}

